package exercises.newcoder.solution;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * <a href="https://www.nowcoder.com/practice/345e2ed5f81d4017bbb8cc6055b0b711?tpId=188&&tqId=38621&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking">
 * NC54 数组中相加和为0的三元组</a>
 *
 * @author or2
 * @Description 给出一个有n个元素的数组S，S中是否有元素a,b,c满足a+b+c=0？找出数组S中所有满足条件的三元组。
 * 注意：
 * 三元组（a、b、c）中的元素必须按非降序排列。（即a≤b≤c）
 * 解集中不能包含重复的三元组。
 * @create 2021年09月04日 时间: 16:08
 */
public class ThreeSum {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
//        存放答案
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
//        初始条件检验
        if (num.length < 3) {
            return ans;
        }
//        使数组有序 (双哨兵快速排序) O(n * log(n))
        Arrays.sort(num);
        for (int i = 0; i < num.length - 2; i++) {
//            左边界 >0 直接退出
            if (num[i] >= 0) {
                break;
            }

//            左边界默认为 i
            int rIndex = num.length - 1;
            int pIndex = i + 1;
//            去重
            if (i > 0 && num[i] == num[i - 1]) {
                continue;
            }

            while (pIndex < rIndex) {
                int sum = num[i] + num[rIndex] + num[pIndex];
//                若得到答案, 缩小区间, 继续检测
                if (sum == 0) {
//                    记录答案
                    ArrayList<Integer> curAns = new ArrayList<>(3);
                    curAns.add(num[i]);
                    curAns.add(num[pIndex]);
                    curAns.add(num[rIndex]);
                    ans.add(curAns);
//                    缩小区间, 继续检测 (可能该左区间存在多解)
                    pIndex++;
                    while (pIndex < rIndex) {
                        if (num[pIndex] != num[pIndex - 1]) {
                            break;
                        }
                        pIndex++;
                    }
                }
                if (sum < 0) {
                    pIndex++;
                } else {
                    rIndex--;
                }
            }
        }
        return ans;
    }
}
